On The Isoperimetric Spectrum of Graphs and Its Approximations

摘要

In this paper we consider higher isoperimetric numbers of a (finite directed)graph. In this regard we focus on the $n$th mean isoperimetric constant of adirected graph as the minimum of the mean outgoing normalized flows from agiven set of $n$ disjoint subsets of the vertex set of the graph. We show thatthe second mean isoperimetric constant in this general setting, coincides with(the mean version of) the classical Cheeger constant of the graph, while forthe rest of the spectrum we show that there is a fundamental difference betweenthe $n$th isoperimetric constant and the number obtained by taking the minimumover all $n$-partitions. In this direction, we show that our definition is thecorrect one in the sense that it satisfies a Federer-Fleming-type theorem, andwe also define and present examples for the concept of a supergeometric graphas a graph whose mean isoperimetric constants are attained on partitions at alllevels. Moreover, considering the ${\bf NP}$-completeness of the isoperimetricproblem on graphs, we address ourselves to the approximation problem where weprove general spectral inequalities that give rise to a general Cheeger-typeinequality as well. On the other hand, we also consider some algorithmicaspects of the problem where we show connections to orthogonal representationsof graphs and following J.~Malik and J.~Shi ($2000$) we study the closerelationships to the well-known $k$-means algorithm and normalized cuts method.